package com.lzq.leetcode.hoot100;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

public class s208 {

    static class Trie {
        private Node root;

        public Trie() {
            root = new Node();
        }

        public void insert(String word) {
            Node p = root;
            for (int i=0; i<word.length(); i++) {
                int c = word.charAt(i) - 'a';
                if (p.val[c] == null) {
                    p.val[c] = new Node();
                }
                p = p.val[c];
            }
            p.isWord = true;
        }

        public boolean search(String word) {

            Node node = getNode(word);
            return node == null ? false : node.isWord;
        }

        public boolean startsWith(String prefix) {

            return getNode(prefix) != null;
        }

        private Node getNode(String s) {

            Node p = root;
            for (int i=0; i<s.length(); i++) {
                int c = s.charAt(i) - 'a';
                if (p.val[c] == null) {
                    return null;
                }
                p = p.val[c];
            }
            return p;
        }

        class Node {

            Node[] val;
            boolean isWord;

            Node() {
                val = new Node[26];
                isWord = false;
            }
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("hotdog");
        System.out.println(trie.startsWith("dog"));
    }
}
